

;=================================================
; retrieves cell from the given env, interpreting
; given env as a list of lists
(defun get-cell (env x y)
 (cond
  ((< y 0) 1)
  ((< x 0) 1)
  ((< y (length env)) (let ((y-list (nth y env)))
                        (if (< x (length y-list))
                         (nth x y-list)
                         1
                         )
                        ))
  (t 1)
 ) ; cond
 ) ; defun get-cell

;=================================================
; represents a solver for shortest-way-finding problems
(defclass WayFinder (AbstractSolver)
 (
  (goal
        :documentation "goal of the solution"
        :accessor goal
        )

  (environment
        :documentation "environment, where solution resides"
        :accessor env

        )

  (possible-moves
        :documentation "moves what finder can perform from certain position"
        :initform '((0 1) (1 0) (0 -1) (-1 0))
        :reader moves
        )

  (steps
        :documentation "temporary member what identifies steps made while searching for a solution"
        :accessor steps
        )

  (solution-steps
        :documentation "solution of a way-finding problem"
        :accessor solution-steps
        )

  )) ; class WayFinder

;=================================================
; reaction on finding a solution
(defun solution-found (finder)
 (if (or
      (equal (solution-steps finder) nil)
      (> (length (solution-steps finder)) (length (steps finder)))
      )
  (setf (solution-steps finder) (reverse (steps finder)))
  )
 ;(format t "sln found: ~a~%" (steps finder))
 )

;=================================================
; checking whether this step already presented
(defun have-step (finder x y)
 (dolist (step-x-y (steps finder))
  (if (and
       (= x (first step-x-y))
       (= y (second step-x-y))
       )
   (return-from have-step t)
   )
  )
 nil ; no such step
 ) ; have-step

;=================================================
; perform searching
(defun traverse (finder x y)

 ; travese through each possible move
 (dolist (move (moves finder))

  ; newX, newY - new position coordinates
  (let ( (newX (+ x (first move))) (newY (+ y (second move))) )

   ; check whether it is possible to make this move
   ; by checking cells in an environment and steps performed before
   (if (and
        (= 0 (get-cell (env finder) newX newY))
        (not (have-step finder newX newY))
       )
    (progn

     ; add this step to an array
     (push (list newX newY) (steps finder))

     ; check whether this step is the solution
     (if (and
          (= newX (first (second (goal finder))))
          (= newY (second (second (goal finder))))
          )
      ; condition is true
      (progn

       (solution-found finder)
       (pop (steps finder))

       ; continuing searching from this point is senseless
       (return-from traverse nil)
       )
      ) ; if newX, newY is a solution

     ; try this one
     (traverse finder newX newY)

     ; remove this step
     (pop (steps finder))
     ) ; progn
    ) ; if get-cell
   ) ; let
  ) ;dolist
  ) ; traverse

(defun start-searching (finder)
 ; reset steps
 (setf (steps finder) nil)

 ; reset solution-steps
 (setf (solution-steps finder) nil)

 ; start traversing from the start cell, specified in a goal
 (let ( (start-x-y (first (goal finder))) )

  ; add first one cell to the steps array
  (push (list (first start-x-y) (second start-x-y)) (steps finder))

  ; do start traversing
  (traverse finder (first start-x-y) (second start-x-y))
 )
 ) ; start-searching

;=================================================
; WayFinder::solve
;
(defmethod solve ((finder WayFinder) env goal)
 (setf (goal finder) goal)
 (setf (env finder) env)

 (start-searching finder)

 ; return 1 solution or nil if a way was not found
 (if (solution-steps finder)
  (list (solution-steps finder))
  nil)
 ) ; solve

;=================================================
; test WayFinder
(defun test-way-finder ()
 (setf solver (make-instance 'WayFinder))
 (setf env
  '(
      (0 0 0 0)
      (0 0 1 1)
      (1 0 1 0)
      (0 0 0 0)
      (0 0 1 0)
      ))
 (setf goal '((0 0) (3 4)))

 (format t "solution: ~a~%" (solve solver env goal))
 )

;=================================================
; test get-cell func
(defun get-cell-dump (env x y)
 (format t "[~a, ~a] = ~a~%" x y (get-cell env x y))
 )

(defun get-cell-multidump (env x-y-list)
 (dolist (x-y x-y-list)
  (get-cell-dump env (first x-y) (second x-y))
  ))

(defun test-get-cell ()
 (setf env
  '(  (0 0 1 0)
      (0 1 1 2)
      (0 0 0 0)
      )
  )

 (get-cell-multidump env '((1 1) (0 0) (0 1) (3 1)))
 )


